﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ClearingGraphAutomaton.Base
{
    partial class Graph
    {
        /// <summary>
        /// Class representing the selection of the nodes of the 2D graph.
        /// </summary>
        public class Selection
        {
            /// <summary>
            /// Creates the instance of the selection consisting of one node 
            /// at the position [row, col].
            /// </summary>
            /// <param name="graph">2D graph.</param>
            /// <param name="row">Row of the node.</param>
            /// <param name="col">Column of the node.</param>
            public Selection(Graph graph, int row, int col)
                : this(graph, row, col, 0, 0)
            {

            }

            /// <summary>
            /// Creates the instance of the selection consisting of one node 
            /// at the position [row, col].
            /// </summary>
            /// <param name="graph">2D graph.</param>
            /// <param name="row">Row of the node.</param>
            /// <param name="col">Column of the node.</param>
            /// <param name="maxDepth">Maximal context depth.</param>
            /// <param name="maxDistance">Maximal context distance.</param>
            public Selection(Graph graph, int row, int col, int maxDepth, int maxDistance)
                : this(graph, row, col, row, col, maxDepth, maxDistance)
            {

            }

            /// <summary>
            /// Creates the instance of the selection consisting of nodes 
            /// placed in the area [topRow .. bottomRow, leftCol .. rightCol].
            /// </summary>
            /// <param name="graph">2D graph.</param>
            /// <param name="topRow">Topmost row of the selection.</param>
            /// <param name="leftCol">Leftmost column of the selection.</param>
            /// <param name="bottomRow">Bottommost row of the selection.</param>
            /// <param name="rightCol">Rightmost column of the selection.</param>
            /// <param name="maxDepth">Maximal context depth.</param>
            /// <param name="maxDistance">Maximal context distance.</param>
            public Selection(Graph graph, int topRow, int leftCol, int bottomRow, int rightCol, int maxDepth, int maxDistance)
            {
                this.graph = graph;
                this.nodeDepthArray = new int[graph.Rows, graph.Columns];
                this.nodeColorArray = new int[graph.Rows, graph.Columns];
                this.AdjustArea(topRow, leftCol, bottomRow, rightCol);
                this.ComputeNodeDepths(maxDepth, maxDistance);
            }

            /// <summary>
            /// True if the selected area contains some nodes.
            /// </summary>
            public bool IsValid { get; protected set; }

            /// <summary>
            /// Topmost row of the selected area.
            /// </summary>
            public int TopmostRow { get; protected set; }

            /// <summary>
            /// Leftmost column of the selected area.
            /// </summary>
            public int LeftmostCol { get; protected set; }

            /// <summary>
            /// Bottommost row of the selected area.
            /// </summary>
            public int BottommostRow { get; protected set; }

            /// <summary>
            /// Rightmost column of the selected area.
            /// </summary>
            public int RightmostCol { get; protected set; }

            /// <summary>
            /// Gets the number of rows in the selected area.
            /// </summary>
            public int Rows
            {
                get
                {
                    if (this.IsValid)
                    {
                        return this.BottommostRow - this.TopmostRow + 1;
                    }
                    else return 0;
                }
            }

            /// <summary>
            /// Gets the number of columns in the selected area.
            /// </summary>
            public int Columns
            {
                get
                {
                    if (this.IsValid)
                    {
                        return this.RightmostCol - this.LeftmostCol + 1;
                    }
                    else return 0;
                }
            }

            /// <summary>
            /// Maximal context depth.
            /// </summary>
            public int MaxContextDepth { get; protected set; }

            /// <summary>
            /// Maximal context distance.
            /// </summary>
            public int MaxContextDistance { get; protected set; }

            /// <summary>
            /// Computed depths of the nodes of the graph from the selection.
            /// </summary>
            public int[,] NodeDepths
            {
                get
                {
                    return this.nodeDepthArray;
                }
            }

            /// <summary>
            /// Returns the Manhattan distance of the given node placed at [row, col] from the selection.
            /// </summary>
            /// <param name="row">Row.</param>
            /// <param name="col">Column.</param>
            /// <returns>Manhattan distance of the node from the selection.</returns>
            public int GetManhattanDistance(int row, int col)
            {
                if (this.IsValid)
                {
                    int rowDistance = Math.Max(Math.Max(this.TopmostRow - row, row - this.BottommostRow), 0);
                    int colDistance = Math.Max(Math.Max(this.LeftmostCol - col, col - this.RightmostCol), 0);
                    return rowDistance + colDistance;
                }
                else return -1;
            }

            /// <summary>
            /// Returns true if the selection contains the specified [row, col] position.
            /// </summary>
            /// <param name="row">Row.</param>
            /// <param name="col">Column.</param>
            /// <returns>True if the selection contains the specified [row, col] position.</returns>
            public bool ContainsPosition(int row, int col)
            {
                if (this.IsValid)
                {
                    return 
                        row >= this.TopmostRow && row <= this.BottommostRow &&
                        col >= this.LeftmostCol && col <= this.RightmostCol;
                }
                else return false;
            }

            /// <summary>
            /// Clears this selection.
            /// </summary>
            public void ClearSelection()
            {
                if (this.IsValid)
                {
                    for (int row = this.TopmostRow; row <= this.BottommostRow; ++row)
                    {
                        for (int col = this.LeftmostCol; col <= this.RightmostCol; ++col)
                        {
                            if (this.graph[row, col] != null)
                            {
                                this.graph.ClearNode(row, col);
                            }
                        }
                    }
                }
            }

            /// <summary>
            /// Resizes the given selection. Returns true if the selection has changed.
            /// </summary>
            /// <param name="topRow">Topmost row of the selection.</param>
            /// <param name="leftCol">Leftmost column of the selection.</param>
            /// <param name="bottomRow">Bottommost row of the selection.</param>
            /// <param name="rightCol">Rightmost column of the selection.</param>
            /// <param name="maxDepth">Maximal context depth.</param>
            /// <param name="maxDistance">Maximal context distance.</param>
            /// <returns>True if the selection has changed.</returns>
            public bool ResizeSelection(int topRow, int leftCol, int bottomRow, int rightCol, int maxDepth, int maxDistance)
            {
                if (this.AdjustArea(topRow, leftCol, bottomRow, rightCol) ||
                    this.MaxContextDepth != maxDepth || this.MaxContextDistance != maxDistance)
                {
                    this.ComputeNodeDepths(maxDepth, maxDistance);
                    return true;
                }
                else return false;
            }

            /// <summary>
            /// Resizes the context of the given selection. Returns true if the selection has changed.
            /// </summary>
            /// <param name="maxDepth">Maximal context depth.</param>
            /// <param name="maxDistance">Maximal context distance.</param>
            /// <returns>True if the selection has changed.</returns>
            public bool ResizeContext(int maxDepth, int maxDistance)
            {
                if (this.MaxContextDepth != maxDepth || this.MaxContextDistance != maxDistance)
                {
                    this.ComputeNodeDepths(maxDepth, maxDistance);
                    return true;
                }
                else return false;
            }

            /// <summary>
            /// Returns string representation of the selection.
            /// </summary>
            /// <returns>String representation of the selection.</returns>
            public string GetSelectionBodyString()
            {
                return this.GetSelectionBodyString(0);
            }

            /// <summary>
            /// Returns string representation of the selection.
            /// </summary>
            /// <param name="depth">Depth of the context.</param>
            /// <returns>String representation of the selection.</returns>
            public string GetSelectionBodyString(int depth)
            {
                if (this.IsValid)
                {
                    return this.GetSelectionBodyString(
                        this.TopmostRow - depth,
                        this.LeftmostCol - depth,
                        this.BottommostRow + depth,
                        this.RightmostCol + depth);
                }
                else return null;
            }

            /// <summary>
            /// Returns string representation of the context of the selection for the specified depth.
            /// </summary>
            /// <param name="maxDepth">Maximal context depth.</param>
            /// <param name="maxDistance">Maximal context distance.</param>
            /// <param name="depthIncreasing">Indicates whether the walk is depth increasing.</param>
            /// <returns>String representation of the context of the selection.</returns>
            public string GetSelectionContextString(int maxDepth, int maxDistance, bool depthIncreasing)
            {
                if (this.IsValid)
                {
                    StringBuilder stringBuilder = new StringBuilder(80 * this.Rows * this.Columns * maxDepth);
                    for (int depth = 1; depth <= maxDepth; ++depth)
                    {
                        stringBuilder.AppendLine(
                            this.GetSelectionContextString(
                                this.TopmostRow,
                                this.LeftmostCol,
                                this.BottommostRow,
                                this.RightmostCol,
                                depth, maxDistance,
                                depthIncreasing));
                    }
                    return stringBuilder.ToString();
                }
                else return null;
            }

            private string GetSelectionBodyString(int topRow, int leftCol, int bottomRow, int rightCol)
            {
                topRow = Math.Min(Math.Max(topRow, 0), this.graph.Rows - 1);
                leftCol = Math.Min(Math.Max(leftCol, 0), this.graph.Columns - 1);
                bottomRow = Math.Min(Math.Max(bottomRow, 0), this.graph.Rows - 1);
                rightCol = Math.Min(Math.Max(rightCol, 0), this.graph.Columns - 1);
                int cols = rightCol - leftCol + 1;
                int rows = bottomRow - topRow + 1;
                bool isValid = (rows > 0 && cols > 0);
                if (isValid)
                {
                    StringBuilder stringBuilder = new StringBuilder(8 * rows * cols);
                    for (int row = topRow; row <= bottomRow; ++row)
                    {
                        for (int col = leftCol; col <= rightCol; ++col)
                        {
                            if (this.graph[row, col] != null)
                            {
                                stringBuilder.Append(this.graph[row, col]);
                            }
                            else
                            {
                                stringBuilder.Append('.');
                            }
                            if (col < rightCol)
                            {
                                stringBuilder.Append('|');
                            }
                            else if (row < bottomRow)
                            {
                                stringBuilder.AppendLine();
                            }
                        }
                    }
                    return stringBuilder.ToString();
                }
                else return null;
            }

            private string GetSelectionContextString(int topRow, int leftCol, int bottomRow, int rightCol, int depth, int maxDistance, bool depthIncreasing)
            {
                topRow = Math.Min(Math.Max(topRow, 0), this.graph.Rows - 1);
                leftCol = Math.Min(Math.Max(leftCol, 0), this.graph.Columns - 1);
                bottomRow = Math.Min(Math.Max(bottomRow, 0), this.graph.Rows - 1);
                rightCol = Math.Min(Math.Max(rightCol, 0), this.graph.Columns - 1);
                int cols = rightCol - leftCol + 1;
                int rows = bottomRow - topRow + 1;
                bool isValid = (rows > 0 && cols > 0);
                if (isValid)
                {
                    StringBuilder stringBuilder = new StringBuilder(80 * rows * cols);
                    for (int row = topRow; row <= bottomRow; ++row)
                    {
                        for (int col = leftCol; col <= rightCol; ++col)
                        {
                            if (this.graph[row, col] != null)
                            {
                                stringBuilder.Append('[');
                                stringBuilder.Append(this.GetDepthFirstWalkString(this.graph[row, col], depth, maxDistance, depthIncreasing));
                                stringBuilder.Append(']');
                                stringBuilder.AppendLine();
                            }
                        }
                    }
                    return stringBuilder.ToString();
                }
                else return null;
            }

            private string GetDepthFirstWalkString(Node node, int depth, int maxDistance, bool depthIncreasing)
            {
                if (node == null)
                {
                    return null;
                }
                StringBuilder stringBuilder = new StringBuilder(8 * depth * depth);
                for (int row = 0; row < this.graph.Rows; ++row)
                {
                    for (int col = 0; col < this.graph.Columns; ++col)
                    {
                        this.nodeColorArray[row, col] = -1;
                    }
                }
                DepthFirstWalkVisit(stringBuilder, node, 0, depth, maxDistance, depthIncreasing);
                return stringBuilder.ToString();
            }

            private void DepthFirstWalkVisit(StringBuilder stringBuilder, Node node, int depth, int maxDepth, int maxDistance, bool depthIncreasing)
            {
                stringBuilder.Append(node.ToString());
                int fromRow = node.Row;
                int fromCol = node.Col;
                this.nodeColorArray[fromRow, fromCol] = 0;
                foreach (Edge edge in node.Edges)
                {
                    Node toNode = edge.ToNode;
                    int toRow = toNode.Row;
                    int toCol = toNode.Col;
                    if ((this.nodeColorArray[toRow, toCol] == -1) && 
                        (depth < maxDepth) && 
                        (maxDistance == 0 || this.GetManhattanDistance(toRow, toCol) <= maxDistance) &&
                        (!depthIncreasing || this.NodeDepths[fromRow, fromCol] < this.NodeDepths[toRow, toCol]))
                    {
                        stringBuilder.Append(edge.ToString());
                        this.DepthFirstWalkVisit(stringBuilder, toNode, depth + 1, maxDepth, maxDistance, depthIncreasing);
                    }
                }
                this.nodeColorArray[fromRow, fromCol] = -1;
                if (depth > 0)
                {
                    stringBuilder.Append("\u21b2");
                }
            }

            private bool AdjustArea(int topRow, int leftCol, int bottomRow, int rightCol)
            {
                topRow = Math.Min(Math.Max(topRow, 0), this.graph.Rows - 1);
                leftCol = Math.Min(Math.Max(leftCol, 0), this.graph.Columns - 1);
                bottomRow = Math.Min(Math.Max(bottomRow, 0), this.graph.Rows - 1);
                rightCol = Math.Min(Math.Max(rightCol, 0), this.graph.Columns - 1);
                int minRow = this.graph.Rows + 1;
                int maxRow = -1;
                int minCol = this.graph.Columns + 1;
                int maxCol = -1;
                for (int row = topRow; row <= bottomRow; ++row)
                {
                    for (int col = leftCol; col <= rightCol; ++col)
                    {
                        if (this.graph[row, col] != null && this.graph[row, col].Color >= 0)
                        {
                            if (row < minRow) minRow = row;
                            if (row > maxRow) maxRow = row;
                            if (col < minCol) minCol = col;
                            if (col > maxCol) maxCol = col;
                        }
                    }
                }
                bool isValid = (minRow <= maxRow && minCol <= maxCol);
                bool changed = (isValid != this.IsValid ||
                    minRow != this.TopmostRow || minCol != this.LeftmostCol ||
                    maxRow != this.BottommostRow || maxCol != this.RightmostCol);
                this.IsValid = isValid;
                this.TopmostRow = minRow;
                this.LeftmostCol = minCol;
                this.BottommostRow = maxRow;
                this.RightmostCol = maxCol;
                return changed;
            }

            private void ComputeNodeDepths(int maxDepth, int maxDistance)
            {
                this.MaxContextDepth = maxDepth;
                this.MaxContextDistance = maxDistance;
                for (int row = 0; row < this.graph.Rows; ++row)
                {
                    for (int col = 0; col < this.graph.Columns; ++col)
                    {
                        nodeDepthArray[row, col] = -1;
                    }
                }
                if (this.IsValid)
                {
                    Queue<Node> queue = new Queue<Node>(8 * this.graph.Rows + 8 * this.graph.Columns);
                    for (int row = this.TopmostRow; row <= this.BottommostRow; ++row)
                    {
                        for (int col = this.LeftmostCol; col <= this.RightmostCol; ++col)
                        {
                            if (this.graph[row, col] != null)
                            {
                                nodeDepthArray[row, col] = 0;
                                queue.Enqueue(this.graph[row, col]);
                            }
                        }
                    }
                    while (queue.Count > 0)
                    {
                        Node fromNode = queue.Dequeue();
                        int fromRow = fromNode.Row;
                        int fromCol = fromNode.Col;
                        foreach (Edge edge in fromNode.Edges)
                        {
                            Node toNode = edge.ToNode;
                            int toRow = toNode.Row;
                            int toCol = toNode.Col;
                            if (nodeDepthArray[toRow, toCol] == -1)
                            {
                                if ((maxDepth == 0 || nodeDepthArray[fromRow, fromCol] + 1 <= maxDepth) &&
                                    (maxDistance == 0 || this.GetManhattanDistance(toRow, toCol) <= maxDistance))
                                {
                                    nodeDepthArray[toRow, toCol] = nodeDepthArray[fromRow, fromCol] + 1;
                                    queue.Enqueue(toNode);
                                }
                            }
                        }
                    }
                }
            }

            private Graph graph;
            private int[,] nodeDepthArray = null;
            private int[,] nodeColorArray = null;
        }
    }
}
